#include "stdio.h"
#include "stdlib.h"

#undef OK
#define OK 1
#undef ERROR
#define ERROR 0
#undef OVERFLOW
#define OVERFLOW -2
#undef NULL
#define NULL 0
typedef char TElemType;
typedef int Status;
typedef struct BiTNode
{ // 结点结构
    TElemType data;
    struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
//以下是建立二叉树存储结构
Status CreateBiTree(BiTree &T)
{
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
        T = NULL;
    else
    {
        //请在此填写代码，将该算法补充完整，参见书本和课件相关章节
        T = (BiTNode *)malloc(sizeof(BiTNode));
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return OK;
}

/**先序遍历  根左右**/
void PreOrder(BiTree T)
{
    if (T)
    {
        printf("%4c", T->data); // 访问结点
        //请在此填写代码，将该算法补充完整，参见书本和课件相关章节
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

/**中序遍历 左根右**/
void InOrder(BiTree T)
{
    if (T)
    {
        //请在此填写代码，将该算法补充完整，参见书本和课件相关章节
        InOrder(T->lchild);
        printf("%4c", T->data);
        InOrder(T->rchild);
    }
}

/**后序遍历 左右根**/
void PostOrder(BiTree T)
{
    //请在此填写代码，将该算法补充完整，参见书本和课件相关章节
    if (T)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%4c", T->data);
    }
}

int main()
{
    BiTree T;
    int s = 0, m = 0, n = 0, d = 0;
    T = NULL;
    printf("\n 请按先序次序输入各结点的值，以#表示空树:\n");
    CreateBiTree(T);
    printf("二叉树已建立完毕！\n");
    printf("\n 先序遍历:");
    PreOrder(T);
    printf("");

    printf("\n 中序遍历:");
    InOrder(T);
    printf("");

    printf("\n 后序遍历:");
    PostOrder(T);
    printf("\n");
    return 0;
}
